Computer graphics is a rapidly-developing and increasingly-important art. It provides one of the essential elements of the technologies commonly referred to as "computer-aided design" and "computer-aided manufacturing" ("CAD/CAM"). Similarly, it is an essential element of a third technology called "computer-aided engineering" ("CAE"). These technologies make possible the presentation on a display device of documents such as engineering drawings, exploded-parts illustrations for service manuals, and business graphs. One of the most useful and valuable aspects of computer graphics is the improvement which allows interaction between the viewer of a displayed image and the image itself. In so-called "interactive computer graphics," the viewer of a displayed image may propose or experimentally make modifications of the displayed image and observe the functional effects of the proposed modifications of the object or document displayed. In order for the aforementioned technologies to be of maximum value, the image shown on the display device should be portrayed in full color.
In the art of computer graphics, there are many available types of display devices. In interactive computer graphics, the most commonly used type of display is the color cathode-ray tube--a highly-developed and well-understood device. The cathode-ray tube is an analog device. That is to say, the position and intensity of each illuminated spot formed on the face of the tube by its electron beam are continuous functions of the respective voltages applied to the deflecting plates and the "electron guns," (usually one for each primary color) of the cathode-ray tube. By contrast, the computer circuitry which furnishes to the cathode-ray tube the data necessary to define each illuminated spot is digital in nature rather than continuous.
When a cathode-ray tube is used in random-scan fashion, a straight line can be drawn on the face of the tube directly from any "addressable" point to any other addressable point on the face of the tube. On the other hand, when a cathode-ray tube is used as the output or display device of a computer-graphics apparatus, it is generally not possible to connect directly any two arbitrarily chosen points on the face of the tube by a straight line having no irregularities. In computer graphics, wherein the display is "rasterized," the face of the cathode-ray tube can be regarded as a matrix of discrete picture elements, or "pixels," each of which can be activated or made bright when it is energized by the electron beam of the cathode-ray tube. Except in certain circumstances, one cannot draw a perfectly straight line from one arbitrary addressable point on the face of the tube to another arbitrary addressable point on the face of the tube. Rather, it is possible only to approximate a straight line by activating a series of pixels as close as possible to the desired path of the line on the face of the tube. Only in the special cases of lines which are horizontal or vertical, or which have a slope with an absolute magnitude of unity, will the activated pixels form the perfectly straight line that is desired. In all other cases, the line which is approximated by a process of "rasterization" will have some degree of irregularity and will only approach--as closely as possible--the desired straight line. This undesired irregularity or stair-step effect is called "aliasing."
Most commonly, the data necessary to implement a rasterized display on a cathode-ray tube are assembled in a device called a "frame buffer." A frame buffer is a large contiguous piece of computer memory. At a minimum, there must be one memory bit in the frame buffer for each pixel of the rasterized image desired to be displayed on the face of the cathode-ray tube. This quantity of memory is called a "bit plane." If the frame buffer contains a single bit plane, the data for the desired image are assembled in the frame buffer one bit at a time. If the display is to be in color, there must be more than one bit plane, and one bit of data can be assembled in each such bit plane at a time.
Before the data stored in the bit planes of the frame buffer can be inputted to the cathode-ray tube, the data must be converted from digital to analog form. This conversion is accomplished by a "digital-to-analog converter" ("DAC"). Each bit of pixel data in the frame buffer must be accessed and converted to analog form before it can appear in the raster on the face of the cathode-ray tube. When color data for the pixels of the display are stored in a plurality of bit planes of the frame buffer, a limited amount of information on the intensities of the respective primary colors is available. The utility of this information can be increased somewhat by feeding the output from the bit planes to "color-look-up tables" having an entry index for each memory element of the respective bit planes of the frame buffer. By means of such color-look-up tables, it is possible to augment the color data received from the bit planes of the frame buffer and to provide the augmented data to the digital-to-analog-converters to be in turn furnished to the respective "color electron guns" of the color-cathode-ray tube in the display device.
In preparing to draw a line in the display, the color data for the pixels which are to be activated must be stored at appropriate addresses in the frame buffer. This is sometimes done by computing and storing the X and Y coordinates of the selected pixels which most nearly approximate the straight line that is desired. Of course, the pixels so selected will in each case depart from the desired straight line by a distance known as the "error." The addresses of the pixels to be activated are furnished to the frame buffer by a "pixel memory controller," which includes or cooperates with a microprocessor that may be in the controller or may be shared with the host computer.
In line-drawing apparatus of the prior art, the microprocessor has computed successive X and Y coordinates for the pixels to be activated. This computation has been carried out by incrementing either the X or Y coordinate by one unit and by determining a "delta value" by which the other coordinate must be adjusted to correspond to the unit incrementation of the first-mentioned coordinate. If the absolute magnitude of the slope of the line to be drawn is less than unity, a prior-art line-drawing apparatus would increment the X coordinate by one unit and then compute the delta value of the Y coordinate, which would be an amount less than unity. On the other hand, if the absolute magnitude of the slope of the line to be drawn is greater than unity, the apparatus would increment the Y coordinate by one unit and would then compute the delta value for the X coordinate which, again, would be an amount less than unity. It was necessary for the microprocessor in prior-art line-drawing apparatus to choose one of the two aforementioned approaches to the computation of the address for each pixel to be successively activated. This choice required "condition testing" by the microprocessor in accordance with the magnitude of the error term. The instructions for such condition testing and for computation of the addresses of successive pixels to be activated were stored in a program memory. A prior-art program for this purpose was developed by J. E. Bresenham and published in an article entitled, "Algorithm for Computer Control of a Digital Plotter," appearing in the IBM System Journal, Vol. 4, Pp. 25-30 in 1965. The so-called "Bresenham Algorithm" has been a very important program in the development of computer-graphics systems. It has undergone a number of modifications to generalize it and to permit the drawing and display of lines having slopes of various magnitudes in any of the eight octants of a Cartesian coordinate system. The instructions to the microprocessor for incrementation and iteration of successive pixel addresses to approximate the desired line may be abbreviated and stated in "program language." A statement of the abbreviated "line-rendering loop" for the first octant as adapted from Bresenham is as follows:
The line end points are (x.sub.1, y.sub.1), and (x.sub.2, Y.sub.2), assumed not equal. PA1 x, y, Del x, Del y are assumed integer. PA1 e is the error term, assumed real. PA1 initialize variables PA1 x=x.sub.1 PA1 y=y.sub.1 PA1 Del x=x.sub.2 -x.sub.1 PA1 Del y=y.sub.2 -y.sub.1 PA1 initialize e to compensate for a non-zero intercept PA1 e=Del y/Del x-1/2 PA1 begin the main loop PA1 for i=1 to Del x PA1 Plot (x, y) PA1 while (e.gtoreq.o) PA1 y=y+1 PA1 e=e-1 PA1 end while PA1 x=x+1 PA1 e=e+Del y/Del x PA1 next i PA1 finish
A flow chart illustrating the implementation of the Bresenham Algorithm appears on page 37 of a book by David F. Rogers entitled Procedural Elements for Computer Graphics, published by McGraw Hill, Inc. in 1985.
Reference to both the "line-rendering loop" set forth above and the flow chart of the Bresenham Algorithm reveals that the microprocessor must perform a step of "condition testing" in which the result of the test depends upon the magnitude of the error term. This condition testing results in so-called "branching inside the loop" of the instructions given to the microprocessor for iteration of the computation of the addresses for successive pixels to be activated in drawing the line in the display. Such condition testing and branching within the loop are very expensive in time of operation of the microprocessor. If the time of operation of the microprocessor is measured in terms of cycles of the "clock" which "strobes" it, each iteration of the loop of the Bresenham Algorithm in the microprocessor may require as many as ten cycles of the clock. In computer graphics, the resolution which can be achieved in the drawing of lines depends inversely on the time required for each operation in the rasterization of the pixels to be activated. Ten cycles of the clock is an undesirably long time for one iteration of the " rendering loop" of the algorithm for computing the address of each pixel of the computer-graphics display. This excessive time element has until now been a limiting factor in the development of the art of computer graphics.